package algo;

import java.util.ArrayDeque;
import java.util.Deque;

public class NumberOfSubArray {
    public static int validSubarrays(int[] nums) {
        int ans = 0;
        for(int i=0;i<nums.length;i++){
            for(int j=i;j<nums.length;j++){
                if(nums[i]<=nums[j]){
                    ans+=1;
                    System.out.println(nums[i]+" "+nums[j]);
                }else break;
            }
        }
        return ans;
    }

    public static int validSubarraysStack(int[] nums) {
        int res = nums.length;
        if(nums.length <= 1) {
            return res;
        }
        res=0;
        Deque<Integer> stack = new ArrayDeque<>();

        for(int i = 0; i < nums.length; i++) {
            int num = nums[i];
            while(!stack.isEmpty() && num < stack.peek()) {
                int tmp = stack.pop();
                System.out.println("pop "+tmp);
            }
            stack.push(num);
            res += stack.size();
            System.out.println("res "+res);

        }
        return res;
    }

    public static void main(String[] args) {
        int ans = NumberOfSubArray.validSubarraysStack(new int[]{1,4,2,5,3});
        System.out.println(ans);
        ans = NumberOfSubArray.validSubarraysStack(new int[]{3,2,1});
        System.out.println(ans);
        ans = NumberOfSubArray.validSubarraysStack(new int[]{2,2,2});
        System.out.println(ans);
    }
}
